﻿// 4924. 矩阵.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>



using namespace std;

//血的教训 列固定 行是递增函数
//行固定 列不是递减函数

/*
https://www.acwing.com/problem/content/4927/

血的教训 列固定 行是递增函数
行固定 列不是递减函数

给定一个 N×N的矩阵 A，行、列编号均为 1∼N，其中第 i行第 j列的元素 Aij等于 i2+100000×i+j2−100000×j+i×j。

请你找到并输出矩阵中第 M 小的元素（即将矩阵中的所有元素从小到大排序后的第 M个元素）。

输入格式
第一行包含整数 T，表示共有 T组测试数据。

每组数据第一行是空行。

第二行包含两个整数 N,M。

输出格式
每组数据输出一行结果，一个整数表示矩阵中第 M 小的元素。

数据范围
1≤T≤12,
1≤N≤50000,
1≤M≤N×N
输入样例：
12

1 1

2 1

2 2

2 3

2 4

3 1

3 2

3 8

3 9

5 1

5 25

5 10
输出样例：
3
-99993
3
12
100007
-199987
-99993
100019
200013
-399969
400031
-99939
*/
const long long N = 50000;
long long t;
long long m, n;

long long calc(long long x, long long y) {
	if(x ==0) return -(3LL * N * N + 100000 * N + 10);
	if (x == n + 1) return (3LL * N * N + 100000 * N + 10);

	long long res = x * x + y * y + (x - y) * 100000LL + x * y;
	return res;
}

long long check(long long x) {
	long long ans = 0;
	for (long long i = 1; i <= n; i++) {
		long long l = 0;  long long r = n + 1LL;
		while (l < r) {
			long long mid = (l + r+1LL) >> 1LL;
			if (calc(mid, i) <= x) {
				l = mid;
			}
			else {
				r = mid - 1LL;
			}
		}
		ans += (l);
		//cout << "# i = " << i <<" .res = " << ans << ". ";
	}

	return ans;
}


void solve() {
	long long r = 3LL*N*N + 100000*N;
	long long  l = -r;
	while (l < r) {
		long long mid = (l + r) >> 1ll;
		//mid = 123456789;
		if (check(mid) >= m) {
			r = mid;
		}
		else {
			l = mid + 1LL;
		}
	}

	cout << l << endl;
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n >> m;
		solve();
	}

	return 0;
}

 